class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if not amount:
            return 0
        dp=[0]*(amount+1)
        for i in coins:
            if i<=amount:
                dp[i]=1
        for i in range(amount+1):
            pos=[] if dp[i]==0 else [dp[i]]
            for j in coins:
                if i-j>0 and dp[i-j]>0:
                 pos.append(dp[i-j]+1)
            dp[i]=min(pos) if pos else 0
        if dp[-1]==0:
            return -1
        return dp[-1]

'''
执行用时：
1164 ms
, 在所有 Python3 提交中击败了
77.02%
的用户
内存消耗：
15 MB
, 在所有 Python3 提交中击败了
53.40%
的用户
'''